The invention relates generally to implementing division methods and apparatus, and in particular to a method and apparatus for implementing the range transformation for division methods in a data processor.
In a data processor, the most time consuming mathematical calculation is division. In order to increase the speed of the division process, some division methods employ a multiplicative technique to converge the divisor towards unity, thus making the dividend converge toward the quotient. These methods are based on a Newton-Raphson method and have the property of quadratic convergence. For example, the IBM model 360/91 computer uses such a technique.
According to this method, the numerator (N) (the dividend) and the denominator (D) (the divisor) of a fraction are each multiplied by a suitable constant "K" so that the denominator has one of the following forms:
1.00000**0XXX PA1 0.11111**1XXX.
Thus, as the denominator approaches one, the numerator will approach the quotient. In accordance with the method, the process can be iterated so that for each subsequent iteration, the number of leading ones or zeros in the denominator fractional portion doubles (or nearly doubles) depending upon the choice of each new "K" which is a function of the new denominator.
There is another class of division methods developed, for example, by Svoboda, and by Krishnamurthi, in which the first method step is similar to the Newton-Raphson method. Thus, according to this second method, the numerator and denominator are multiplied by a constant to place the denominator into one of the two forms noted above. Thereafter, a restoring or non-restoring higher radix division can be performed. If there are "n" leading ones or zeros, a radix of 2.sup.n can be employed. Each successive quotient digit in that radix then becomes a simple transformation of the most significant bits of the then current partial remainder. An improvement of this method is described in copending U.S. application Ser. No. 701,556, filed Feb. 14, 1985 and assigned to the asignee of this invention.
Both of the above-described methods therefore require an efficient method and apparatus for transforming the original denominator, D, into its desired form. Typically, either a brute force table look-up approach has been employed, wherein the value of D is used to determine the multiplicative product transform value K or an iterative approach, wherein two leading digits are employed to find a value K which, after multiplication, will add an additional "one" or "zero" in the transformed denominator, is used. These methods, however, are either expensive (in hardware requirements) or slow.
It is therefore an object of the invention to efficiently transform a normalized denominator into a form for use with a division method requiring range transformed coefficients. Other objects of the invention are a low cost, reliable hardware circuitry for effecting a transform of the divisor for use in the above-described division techniques.